package leetcode.top100;

import offerbook.Code66_HasPathInMatrix;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 * <p>
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，
 * <p>
 * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * <p>
 * 同一个单元格内的字母不允许被重复使用。
 * <p>
 * 示例:
 * <p>
 * board =
 * [
 * <p>
 * ['A','B','C','E'],
 * <p>
 * ['S','F','C','S'],
 * <p>
 * ['A','D','E','E']
 * <p>
 * ]
 * <p>
 * 给定 word = "ABCCED", 返回 true.
 * <p>
 * 给定 word = "SEE", 返回 true.
 * <p>
 * 给定 word = "ABCB", 返回 false.
 * <p>
 * 这题是回溯，及时标记和清除标记。
 * 见{@link Code66_HasPathInMatrix}
 *
 * @since 2019/12/3 0003 下午 10:59
 */
public class Code79_SearchWord {

    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word1 = "ABCCED";
        String word2 = "SEE";
        String word3 = "ABCB";

        System.out.println(exist(board, word1));
        System.out.println(exist(board, word2));
        System.out.println(exist(board, word3));

    }

    public static boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.length() == 0) return false;
        int row = board.length;
        int col = board[0].length;
        boolean visited[][] = new boolean[row][col];
        //对每个节点进行前后左右搜索。并且伴有回溯和设置访问flag
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(doExist(board, word, visited, i, j, 0, row, col))
                    return true;
            }
            
        }
        return false;
    }

    private static boolean doExist(char[][] board, String word, boolean[][] visited,
                                   int i, int j, int index, int row, int col) {
        //base case 1
        if (index == word.length()) return true;

        //base case 2
        if (i < 0 || i >= row || j < 0 || j >= col) return false;

        //如果当前位置相等，则继续遍历前后左右
        if (board[i][j] == word.charAt(index) && !visited[i][j]) {
            visited[i][j] = true;
            //从当前位置上下左右遍历
            boolean res =
                    doExist(board, word, visited, i - 1, j, index + 1, row, col) ||
                            doExist(board, word, visited, i + 1, j, index + 1, row, col) ||
                            doExist(board, word, visited, i, j - 1, index + 1, row, col) ||
                            doExist(board, word, visited, i, j + 1, index + 1, row, col);
            if (!res) {
                //否则从当前位置[i,j] 走没有找到匹配的，回溯。并重置当前位置。给从新的一开始的起点开始用。
                visited[i][j] = false;
            }
            return res;
        } else {
            return false;
        }
    }
}
